{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第5章 决策树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个**if-then**规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。\n",
    "\n",
    "2．决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是NP完全问题。现实中采用启发式方法学习次优的决策树。\n",
    "\n",
    "决策树学习算法包括3部分：特征选择、树的生成和树的剪枝。常用的算法有ID3、\n",
    "C4.5和CART。\n",
    "\n",
    "3．特征选择的目的在于选取对训练数据能够分类的特征。特征选择的关键是其准则。常用的准则如下：\n",
    "\n",
    "（1）样本集合$D$对特征$A$的信息增益（ID3）\n",
    "\n",
    "\n",
    "$$g(D, A)=H(D)-H(D|A)$$\n",
    "\n",
    "$$H(D)=-\\sum_{k=1}^{K} \\frac{\\left|C_{k}\\right|}{|D|} \\log _{2} \\frac{\\left|C_{k}\\right|}{|D|}$$\n",
    "\n",
    "$$H(D | A)=\\sum_{i=1}^{n} \\frac{\\left|D_{i}\\right|}{|D|} H\\left(D_{i}\\right)$$\n",
    "\n",
    "其中，$H(D)$是数据集$D$的熵，$H(D_i)$是数据集$D_i$的熵，$H(D|A)$是数据集$D$对特征$A$的条件熵。\t$D_i$是$D$中特征$A$取第$i$个值的样本子集，$C_k$是$D$中属于第$k$类的样本子集。$n$是特征$A$取 值的个数，$K$是类的个数。\n",
    "\n",
    "（2）样本集合$D$对特征$A$的信息增益比（C4.5）\n",
    "\n",
    "\n",
    "$$g_{R}(D, A)=\\frac{g(D, A)}{H(D)}$$\n",
    "\n",
    "\n",
    "其中，$g(D,A)$是信息增益，$H(D)$是数据集$D$的熵。\n",
    "\n",
    "（3）样本集合$D$的基尼指数（CART）\n",
    "\n",
    "$$\\operatorname{Gini}(D)=1-\\sum_{k=1}^{K}\\left(\\frac{\\left|C_{k}\\right|}{|D|}\\right)^{2}$$\n",
    "\n",
    "特征$A$条件下集合$D$的基尼指数：\n",
    "\n",
    " $$\\operatorname{Gini}(D, A)=\\frac{\\left|D_{1}\\right|}{|D|} \\operatorname{Gini}\\left(D_{1}\\right)+\\frac{\\left|D_{2}\\right|}{|D|} \\operatorname{Gini}\\left(D_{2}\\right)$$\n",
    " \n",
    "4．决策树的生成。通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根结点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。\n",
    "\n",
    "5．决策树的剪枝。由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from collections import Counter\n",
    "import math\n",
    "from math import log\n",
    "import pprint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 书上题目5.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 书上题目5.1\n",
    "def create_data():\n",
    "    datasets = [['青年', '否', '否', '一般', '否'],\n",
    "               ['青年', '否', '否', '好', '否'],\n",
    "               ['青年', '是', '否', '好', '是'],\n",
    "               ['青年', '是', '是', '一般', '是'],\n",
    "               ['青年', '否', '否', '一般', '否'],\n",
    "               ['中年', '否', '否', '一般', '否'],\n",
    "               ['中年', '否', '否', '好', '否'],\n",
    "               ['中年', '是', '是', '好', '是'],\n",
    "               ['中年', '否', '是', '非常好', '是'],\n",
    "               ['中年', '否', '是', '非常好', '是'],\n",
    "               ['老年', '否', '是', '非常好', '是'],\n",
    "               ['老年', '否', '是', '好', '是'],\n",
    "               ['老年', '是', '否', '好', '是'],\n",
    "               ['老年', '是', '否', '非常好', '是'],\n",
    "               ['老年', '否', '否', '一般', '否'],\n",
    "               ]\n",
    "    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']\n",
    "    # 返回数据集和每个维度的名称\n",
    "    return datasets, labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "datasets, labels = create_data()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_data = pd.DataFrame(datasets, columns=labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>青年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>一般</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>青年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>好</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>青年</td>\n",
       "      <td>是</td>\n",
       "      <td>否</td>\n",
       "      <td>好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>青年</td>\n",
       "      <td>是</td>\n",
       "      <td>是</td>\n",
       "      <td>一般</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>青年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>一般</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>中年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>一般</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>中年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>好</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>中年</td>\n",
       "      <td>是</td>\n",
       "      <td>是</td>\n",
       "      <td>好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>中年</td>\n",
       "      <td>否</td>\n",
       "      <td>是</td>\n",
       "      <td>非常好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>中年</td>\n",
       "      <td>否</td>\n",
       "      <td>是</td>\n",
       "      <td>非常好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>老年</td>\n",
       "      <td>否</td>\n",
       "      <td>是</td>\n",
       "      <td>非常好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>老年</td>\n",
       "      <td>否</td>\n",
       "      <td>是</td>\n",
       "      <td>好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>老年</td>\n",
       "      <td>是</td>\n",
       "      <td>否</td>\n",
       "      <td>好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>老年</td>\n",
       "      <td>是</td>\n",
       "      <td>否</td>\n",
       "      <td>非常好</td>\n",
       "      <td>是</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>老年</td>\n",
       "      <td>否</td>\n",
       "      <td>否</td>\n",
       "      <td>一般</td>\n",
       "      <td>否</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄 有工作 有自己的房子 信贷情况 类别\n",
       "0   青年   否      否   一般  否\n",
       "1   青年   否      否    好  否\n",
       "2   青年   是      否    好  是\n",
       "3   青年   是      是   一般  是\n",
       "4   青年   否      否   一般  否\n",
       "5   中年   否      否   一般  否\n",
       "6   中年   否      否    好  否\n",
       "7   中年   是      是    好  是\n",
       "8   中年   否      是  非常好  是\n",
       "9   中年   否      是  非常好  是\n",
       "10  老年   否      是  非常好  是\n",
       "11  老年   否      是    好  是\n",
       "12  老年   是      否    好  是\n",
       "13  老年   是      否  非常好  是\n",
       "14  老年   否      否   一般  否"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 熵\n",
    "def calc_ent(datasets):\n",
    "    data_length = len(datasets)\n",
    "    label_count = {}\n",
    "    for i in range(data_length):\n",
    "        label = datasets[i][-1]\n",
    "        if label not in label_count:\n",
    "            label_count[label] = 0\n",
    "        label_count[label] += 1\n",
    "    ent = -sum([(p / data_length) * log(p / data_length, 2)\n",
    "                for p in label_count.values()])\n",
    "    return ent\n",
    "# def entropy(y):\n",
    "#     \"\"\"\n",
    "#     Entropy of a label sequence\n",
    "#     \"\"\"\n",
    "#     hist = np.bincount(y)\n",
    "#     ps = hist / np.sum(hist)\n",
    "#     return -np.sum([p * np.log2(p) for p in ps if p > 0])\n",
    "\n",
    "\n",
    "# 经验条件熵\n",
    "def cond_ent(datasets, axis=0):\n",
    "    data_length = len(datasets)\n",
    "    feature_sets = {}\n",
    "    for i in range(data_length):\n",
    "        feature = datasets[i][axis]\n",
    "        if feature not in feature_sets:\n",
    "            feature_sets[feature] = []\n",
    "        feature_sets[feature].append(datasets[i])\n",
    "    cond_ent = sum(\n",
    "        [(len(p) / data_length) * calc_ent(p) for p in feature_sets.values()])\n",
    "    return cond_ent\n",
    "\n",
    "\n",
    "# 信息增益\n",
    "def info_gain(ent, cond_ent):\n",
    "    return ent - cond_ent\n",
    "\n",
    "\n",
    "def info_gain_train(datasets):\n",
    "    count = len(datasets[0]) - 1\n",
    "    ent = calc_ent(datasets)\n",
    "#     ent = entropy(datasets)\n",
    "    best_feature = []\n",
    "    for c in range(count):\n",
    "        c_info_gain = info_gain(ent, cond_ent(datasets, axis=c))\n",
    "        best_feature.append((c, c_info_gain))\n",
    "        print('特征({}) - info_gain - {:.3f}'.format(labels[c], c_info_gain))\n",
    "    # 比较大小\n",
    "    best_ = max(best_feature, key=lambda x: x[-1])\n",
    "    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "特征(年龄) - info_gain - 0.083\n",
      "特征(有工作) - info_gain - 0.324\n",
      "特征(有自己的房子) - info_gain - 0.420\n",
      "特征(信贷情况) - info_gain - 0.363\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'特征(有自己的房子)的信息增益最大，选择为根节点特征'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "info_gain_train(np.array(datasets))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "---\n",
    "\n",
    "利用ID3算法生成决策树，例5.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义节点类 二叉树\n",
    "class Node:\n",
    "    def __init__(self, root=True, label=None, feature_name=None, feature=None):\n",
    "        self.root = root\n",
    "        self.label = label\n",
    "        self.feature_name = feature_name\n",
    "        self.feature = feature\n",
    "        self.tree = {}\n",
    "        self.result = {\n",
    "            'label:': self.label,\n",
    "            'feature': self.feature,\n",
    "            'tree': self.tree\n",
    "        }\n",
    "\n",
    "    def __repr__(self):\n",
    "        return '{}'.format(self.result)\n",
    "\n",
    "    def add_node(self, val, node):\n",
    "        self.tree[val] = node\n",
    "\n",
    "    def predict(self, features):\n",
    "        if self.root is True:\n",
    "            return self.label\n",
    "        return self.tree[features[self.feature]].predict(features)\n",
    "\n",
    "\n",
    "class DTree:\n",
    "    def __init__(self, epsilon=0.1):\n",
    "        self.epsilon = epsilon\n",
    "        self._tree = {}\n",
    "\n",
    "    # 熵\n",
    "    @staticmethod\n",
    "    def calc_ent(datasets):\n",
    "        data_length = len(datasets)\n",
    "        label_count = {}\n",
    "        for i in range(data_length):\n",
    "            label = datasets[i][-1]\n",
    "            if label not in label_count:\n",
    "                label_count[label] = 0\n",
    "            label_count[label] += 1\n",
    "        ent = -sum([(p / data_length) * log(p / data_length, 2)\n",
    "                    for p in label_count.values()])\n",
    "        return ent\n",
    "\n",
    "    # 经验条件熵\n",
    "    def cond_ent(self, datasets, axis=0):\n",
    "        data_length = len(datasets)\n",
    "        feature_sets = {}\n",
    "        for i in range(data_length):\n",
    "            feature = datasets[i][axis]\n",
    "            if feature not in feature_sets:\n",
    "                feature_sets[feature] = []\n",
    "            feature_sets[feature].append(datasets[i])\n",
    "        cond_ent = sum([(len(p) / data_length) * self.calc_ent(p)\n",
    "                        for p in feature_sets.values()])\n",
    "        return cond_ent\n",
    "\n",
    "    # 信息增益\n",
    "    @staticmethod\n",
    "    def info_gain(ent, cond_ent):\n",
    "        return ent - cond_ent\n",
    "\n",
    "    def info_gain_train(self, datasets):\n",
    "        count = len(datasets[0]) - 1\n",
    "        ent = self.calc_ent(datasets)\n",
    "        best_feature = []\n",
    "        for c in range(count):\n",
    "            c_info_gain = self.info_gain(ent, self.cond_ent(datasets, axis=c))\n",
    "            best_feature.append((c, c_info_gain))\n",
    "        # 比较大小\n",
    "        best_ = max(best_feature, key=lambda x: x[-1])\n",
    "        return best_\n",
    "\n",
    "    def train(self, train_data):\n",
    "        \"\"\"\n",
    "        input:数据集D(DataFrame格式)，特征集A，阈值eta\n",
    "        output:决策树T\n",
    "        \"\"\"\n",
    "        _, y_train, features = train_data.iloc[:, :\n",
    "                                               -1], train_data.iloc[:,\n",
    "                                                                    -1], train_data.columns[:\n",
    "                                                                                            -1]\n",
    "        # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T\n",
    "        if len(y_train.value_counts()) == 1:\n",
    "            return Node(root=True, label=y_train.iloc[0])\n",
    "\n",
    "        # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T\n",
    "        if len(features) == 0:\n",
    "            return Node(\n",
    "                root=True,\n",
    "                label=y_train.value_counts().sort_values(\n",
    "                    ascending=False).index[0])\n",
    "\n",
    "        # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征\n",
    "        max_feature, max_info_gain = self.info_gain_train(np.array(train_data))\n",
    "        max_feature_name = features[max_feature]\n",
    "\n",
    "        # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T\n",
    "        if max_info_gain < self.epsilon:\n",
    "            return Node(\n",
    "                root=True,\n",
    "                label=y_train.value_counts().sort_values(\n",
    "                    ascending=False).index[0])\n",
    "\n",
    "        # 5,构建Ag子集\n",
    "        node_tree = Node(\n",
    "            root=False, feature_name=max_feature_name, feature=max_feature)\n",
    "\n",
    "        feature_list = train_data[max_feature_name].value_counts().index\n",
    "        for f in feature_list:\n",
    "            sub_train_df = train_data.loc[train_data[max_feature_name] ==\n",
    "                                          f].drop([max_feature_name], axis=1)\n",
    "\n",
    "            # 6, 递归生成树\n",
    "            sub_tree = self.train(sub_train_df)\n",
    "            node_tree.add_node(f, sub_tree)\n",
    "\n",
    "        # pprint.pprint(node_tree.tree)\n",
    "        return node_tree\n",
    "\n",
    "    def fit(self, train_data):\n",
    "        self._tree = self.train(train_data)\n",
    "        return self._tree\n",
    "\n",
    "    def predict(self, X_test):\n",
    "        return self._tree.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "datasets, labels = create_data()\n",
    "data_df = pd.DataFrame(datasets, columns=labels)\n",
    "dt = DTree()\n",
    "tree = dt.fit(data_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'label:': None, 'feature': 2, 'tree': {'否': {'label:': None, 'feature': 1, 'tree': {'否': {'label:': '否', 'feature': None, 'tree': {}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'否'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dt.predict(['老年', '否', '否', '一般'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### scikit-learn实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data\n",
    "def create_data():\n",
    "    iris = load_iris()\n",
    "    df = pd.DataFrame(iris.data, columns=iris.feature_names)\n",
    "    df['label'] = iris.target\n",
    "    df.columns = [\n",
    "        'sepal length', 'sepal width', 'petal length', 'petal width', 'label'\n",
    "    ]\n",
    "    data = np.array(df.iloc[:100, [0, 1, -1]])\n",
    "    # print(data)\n",
    "    return data[:, :2], data[:, -1]\n",
    "\n",
    "\n",
    "X, y = create_data()\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.tree import export_graphviz\n",
    "import graphviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeClassifier()"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf = DecisionTreeClassifier()\n",
    "clf.fit(X_train, y_train,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9666666666666667"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_pic = export_graphviz(clf, out_file=\"mytree.pdf\")\n",
    "with open('mytree.pdf') as f:\n",
    "    dot_graph = f.read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: Tree Pages: 1 -->\r\n",
       "<svg width=\"495pt\" height=\"373pt\"\r\n",
       " viewBox=\"0.00 0.00 495.00 373.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 369)\">\r\n",
       "<title>Tree</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-369 491,-369 491,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"322.5,-365 218.5,-365 218.5,-297 322.5,-297 322.5,-365\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"270.5\" y=\"-349.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X[0] &lt;= 5.45</text>\r\n",
       "<text text-anchor=\"middle\" x=\"270.5\" y=\"-334.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.5</text>\r\n",
       "<text text-anchor=\"middle\" x=\"270.5\" y=\"-319.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 70</text>\r\n",
       "<text text-anchor=\"middle\" x=\"270.5\" y=\"-304.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [35, 35]</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"261.5,-261 163.5,-261 163.5,-193 261.5,-193 261.5,-261\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-245.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X[1] &lt;= 2.8</text>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-230.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.153</text>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-215.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 36</text>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-200.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [33, 3]</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M251.669,-296.884C246.807,-288.332 241.508,-279.013 236.423,-270.072\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"239.421,-268.262 231.435,-261.299 233.335,-271.722 239.421,-268.262\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"224.806\" y=\"-281.704\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">True</text>\r\n",
       "</g>\r\n",
       "<!-- 6 -->\r\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"377.5,-261 279.5,-261 279.5,-193 377.5,-193 377.5,-261\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-245.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X[1] &lt;= 3.45</text>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-230.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.111</text>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-215.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 34</text>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-200.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [2, 32]</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;6 -->\r\n",
       "<g id=\"edge6\" class=\"edge\"><title>0&#45;&gt;6</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M289.331,-296.884C294.193,-288.332 299.492,-279.013 304.577,-270.072\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.665,-271.722 309.565,-261.299 301.579,-268.262 307.665,-271.722\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"316.194\" y=\"-281.704\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">False</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"145,-157 54,-157 54,-89 145,-89 145,-157\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-141.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X[0] &lt;= 4.7</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-126.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.375</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-111.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 4</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-96.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [1, 3]</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M175.812,-192.884C165.648,-183.709 154.505,-173.65 143.95,-164.123\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"146.159,-161.402 136.39,-157.299 141.468,-166.598 146.159,-161.402\"/>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"261.5,-149.5 163.5,-149.5 163.5,-96.5 261.5,-96.5 261.5,-149.5\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-134.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-119.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 32</text>\r\n",
       "<text text-anchor=\"middle\" x=\"212.5\" y=\"-104.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [32, 0]</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\"><title>1&#45;&gt;5</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M212.5,-192.884C212.5,-182.326 212.5,-170.597 212.5,-159.854\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"216,-159.52 212.5,-149.52 209,-159.52 216,-159.52\"/>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"91,-53 0,-53 0,-0 91,-0 91,-53\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-37.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-22.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 1</text>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-7.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [1, 0]</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M80.6134,-88.9485C75.6474,-80.2579 70.2776,-70.8608 65.2667,-62.0917\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"68.207,-60.1826 60.2067,-53.2367 62.1293,-63.6557 68.207,-60.1826\"/>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"200,-53 109,-53 109,-0 200,-0 200,-53\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-37.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-22.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 3</text>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-7.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [0, 3]</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>2&#45;&gt;4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M118.736,-88.9485C123.794,-80.2579 129.264,-70.8608 134.367,-62.0917\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"137.516,-63.6401 139.521,-53.2367 131.466,-60.1189 137.516,-63.6401\"/>\r\n",
       "</g>\r\n",
       "<!-- 7 -->\r\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"377.5,-149.5 279.5,-149.5 279.5,-96.5 377.5,-96.5 377.5,-149.5\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-134.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-119.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 32</text>\r\n",
       "<text text-anchor=\"middle\" x=\"328.5\" y=\"-104.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [0, 32]</text>\r\n",
       "</g>\r\n",
       "<!-- 6&#45;&gt;7 -->\r\n",
       "<g id=\"edge7\" class=\"edge\"><title>6&#45;&gt;7</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M328.5,-192.884C328.5,-182.326 328.5,-170.597 328.5,-159.854\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"332,-159.52 328.5,-149.52 325,-159.52 332,-159.52\"/>\r\n",
       "</g>\r\n",
       "<!-- 8 -->\r\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"487,-149.5 396,-149.5 396,-96.5 487,-96.5 487,-149.5\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"441.5\" y=\"-134.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"441.5\" y=\"-119.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 2</text>\r\n",
       "<text text-anchor=\"middle\" x=\"441.5\" y=\"-104.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [2, 0]</text>\r\n",
       "</g>\r\n",
       "<!-- 6&#45;&gt;8 -->\r\n",
       "<g id=\"edge8\" class=\"edge\"><title>6&#45;&gt;8</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M365.188,-192.884C378.103,-181.226 392.599,-168.141 405.46,-156.532\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"408.15,-158.819 413.228,-149.52 403.46,-153.622 408.15,-158.819\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1e1dd561608>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graphviz.Source(dot_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第5章决策树-习题\n",
    "\n",
    "### 习题5.1\n",
    "根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "\n",
    "表5.1 贷款申请样本数据表  \n",
    "\n",
    "ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别\n",
    ":-: | :-: | :-: | :-: | :-: | :-: \n",
    "1 | 青年 | 否 | 否 | 一般 | 否\n",
    "2 | 青年 | 否 | 否 | 好 | 否\n",
    "3 | 青年 | 是 | 否 | 好 | 是\n",
    "4 | 青年 | 是 | 是 | 一般 | 是\n",
    "5 | 青年 | 否 | 否 | 一般 | 否\n",
    "6 | 中年 | 否 | 否 | 一般 | 否\n",
    "7 | 中年 | 否 | 否 | 好 | 否\n",
    "8 | 中年 | 是 | 是 | 好 | 是\n",
    "9 | 中年 | 否 | 是 | 非常好 | 是\n",
    "10 | 中年 | 否 | 是 | 非常好 | 是\n",
    "11 | 老年 | 否 | 是 | 非常好 | 是\n",
    "12 | 老年 | 否 | 是 | 好 | 是\n",
    "13 | 老年 | 是 | 否 | 好 | 是\n",
    "14 | 老年 | 是 | 否 | 非常好 | 是\n",
    "15 | 老年 | 否 | 否 | 一般 | 否"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: Tree Pages: 1 -->\r\n",
       "<svg width=\"277pt\" height=\"314pt\"\r\n",
       " viewBox=\"0.00 0.00 277.00 314.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 310)\">\r\n",
       "<title>Tree</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-310 273,-310 273,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\r\n",
       "<path fill=\"#bddef6\" stroke=\"black\" d=\"M210,-306C210,-306 115,-306 115,-306 109,-306 103,-300 103,-294 103,-294 103,-235 103,-235 103,-229 109,-223 115,-223 115,-223 210,-223 210,-223 216,-223 222,-229 222,-235 222,-235 222,-294 222,-294 222,-300 216,-306 210,-306\"/>\r\n",
       "<text text-anchor=\"start\" x=\"111\" y=\"-290.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">有自己的房子 ≤ 3.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"129\" y=\"-275.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.48</text>\r\n",
       "<text text-anchor=\"start\" x=\"119\" y=\"-260.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 15</text>\r\n",
       "<text text-anchor=\"start\" x=\"122\" y=\"-245.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 9]</text>\r\n",
       "<text text-anchor=\"start\" x=\"133.5\" y=\"-230.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 1</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\r\n",
       "<path fill=\"#f2c09c\" stroke=\"black\" d=\"M142,-187C142,-187 69,-187 69,-187 63,-187 57,-181 57,-175 57,-175 57,-116 57,-116 57,-110 63,-104 69,-104 69,-104 142,-104 142,-104 148,-104 154,-110 154,-116 154,-116 154,-175 154,-175 154,-181 148,-187 142,-187\"/>\r\n",
       "<text text-anchor=\"start\" x=\"70.5\" y=\"-171.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">有工作 ≤ 3.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"68\" y=\"-156.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.444</text>\r\n",
       "<text text-anchor=\"start\" x=\"66\" y=\"-141.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 9</text>\r\n",
       "<text text-anchor=\"start\" x=\"65\" y=\"-126.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"76.5\" y=\"-111.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 0</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M142.724,-222.907C138.524,-214.286 134.044,-205.09 129.701,-196.175\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.767,-194.478 125.241,-187.021 126.474,-197.544 132.767,-194.478\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"117.091\" y=\"-206.955\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">True</text>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\r\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M257,-179.5C257,-179.5 184,-179.5 184,-179.5 178,-179.5 172,-173.5 172,-167.5 172,-167.5 172,-123.5 172,-123.5 172,-117.5 178,-111.5 184,-111.5 184,-111.5 257,-111.5 257,-111.5 263,-111.5 269,-117.5 269,-123.5 269,-123.5 269,-167.5 269,-167.5 269,-173.5 263,-179.5 257,-179.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"191.5\" y=\"-164.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"181\" y=\"-149.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 6</text>\r\n",
       "<text text-anchor=\"start\" x=\"180\" y=\"-134.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 6]</text>\r\n",
       "<text text-anchor=\"start\" x=\"191.5\" y=\"-119.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 1</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M182.623,-222.907C188.093,-211.873 194.029,-199.898 199.544,-188.773\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"202.753,-190.181 204.058,-179.667 196.481,-187.072 202.753,-190.181\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"212.045\" y=\"-199.657\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">False</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\r\n",
       "<path fill=\"#e58139\" stroke=\"black\" d=\"M85,-68C85,-68 12,-68 12,-68 6,-68 0,-62 0,-56 0,-56 0,-12 0,-12 0,-6 6,-0 12,-0 12,-0 85,-0 85,-0 91,-0 97,-6 97,-12 97,-12 97,-56 97,-56 97,-62 91,-68 85,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"19.5\" y=\"-52.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"9\" y=\"-37.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 6</text>\r\n",
       "<text text-anchor=\"start\" x=\"8\" y=\"-22.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"19.5\" y=\"-7.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 0</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M84.2753,-103.726C79.7649,-95.0615 74.9939,-85.8962 70.4568,-77.1802\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"73.556,-75.5537 65.834,-68.2996 67.3469,-78.7859 73.556,-75.5537\"/>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\r\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M200,-68C200,-68 127,-68 127,-68 121,-68 115,-62 115,-56 115,-56 115,-12 115,-12 115,-6 121,-0 127,-0 127,-0 200,-0 200,-0 206,-0 212,-6 212,-12 212,-12 212,-56 212,-56 212,-62 206,-68 200,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"134.5\" y=\"-52.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"124\" y=\"-37.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 3</text>\r\n",
       "<text text-anchor=\"start\" x=\"123\" y=\"-22.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"134.5\" y=\"-7.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 1</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>1&#45;&gt;3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.097,-103.726C131.687,-95.0615 136.541,-85.8962 141.158,-77.1802\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"144.274,-78.7748 145.862,-68.2996 138.088,-75.4982 144.274,-78.7748\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x1e1dd2102c8>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn import preprocessing\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn import tree\n",
    "import graphviz\n",
    "\n",
    "features = [\"年龄\", \"有工作\", \"有自己的房子\", \"信贷情况\"]\n",
    "X_train = pd.DataFrame([\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"是\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"好\"],\n",
    "    [\"中年\", \"是\", \"是\", \"好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"否\", \"一般\"]\n",
    "])\n",
    "y_train = pd.DataFrame([\"否\", \"否\", \"是\", \"是\", \"否\", \n",
    "                        \"否\", \"否\", \"是\", \"是\", \"是\", \n",
    "                        \"是\", \"是\", \"是\", \"是\", \"否\"])\n",
    "# 数据预处理\n",
    "le_x = preprocessing.LabelEncoder()\n",
    "le_x.fit(np.unique(X_train))\n",
    "X_train = X_train.apply(le_x.transform)\n",
    "le_y = preprocessing.LabelEncoder()\n",
    "le_y.fit(np.unique(y_train))\n",
    "y_train = y_train.apply(le_y.transform)\n",
    "# 调用sklearn.DT建立训练模型\n",
    "model_tree = DecisionTreeClassifier()\n",
    "model_tree.fit(X_train, y_train)\n",
    "\n",
    "# 可视化\n",
    "dot_data = tree.export_graphviz(model_tree, out_file=None,\n",
    "                                    feature_names=features,\n",
    "                                    class_names=[str(k) for k in np.unique(y_train)],\n",
    "                                    filled=True, rounded=True,\n",
    "                                    special_characters=True)\n",
    "graph = graphviz.Source(dot_data)\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题5.2\n",
    "&emsp;&emsp;已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。  \n",
    "表5.2 训练数据表  \n",
    "\n",
    "| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |  \n",
    "| - | - | - | - | - | - | - | - | - | - | - |  \n",
    "| $y_i$ | 4.50 | 4.75 | 4.91 | 5.34 | 5.80 | 7.05 | 7.90 | 8.23 | 8.70 | 9.00"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "&emsp;&emsp;决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。  \n",
    "> 算法5.5（最小二乘回归树生成算法）  \n",
    "输入：训练数据集$D$  \n",
    "输出：回归树$f(x)$  \n",
    "在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树；  \n",
    "(1)选择最优切分变量$j$与切分点$s$，求解$$\\min_{j,s} \\left[ \\min_{c_1} \\sum_{x_i \\in R_1(j,s)} (y_i - c_1)^2 + \\min_{c_2} \\sum_{x_i \\in R_2(j,s)} (y_i - c_2)^2\\right]$$遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，选择使得上式达到最小值的对$(j,s)$  \n",
    "(2)用选定的对$(j,s)$划分区域并决定相应的输出值：$$R_1(j,s)=\\{x|x^{(j)}\\leqslant s\\}, R_2(j,s)=\\{x|x^{(j)} > s\\} \\\\ \n",
    "\\hat{c_m} = \\frac{1}{N_m} \\sum_{x_i \\in R_m(j,s)} y_i, x \\in R_m, m=1,2 $$\n",
    "(3)继续对两个子区域调用步骤(1),(2)，直至满足停止条件  \n",
    "(4)将输入空间划分为$M$个区域$R_1,R_2,\\cdots,R_M$，生成决策树：$$f(x)=\\sum_{m=1}^M \\hat{c_m} I(x \\in R_m)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "class LeastSqRTree:\n",
    "    def __init__(self, train_X, y, epsilon):\n",
    "        # 训练集特征值\n",
    "        self.x = train_X\n",
    "        # 类别\n",
    "        self.y = y\n",
    "        # 特征总数\n",
    "        self.feature_count = train_X.shape[1]\n",
    "        # 损失阈值\n",
    "        self.epsilon = epsilon\n",
    "        # 回归树\n",
    "        self.tree = None\n",
    "\n",
    "    def _fit(self, x, y, feature_count, epsilon):\n",
    "        # 选择最优切分点变量j与切分点s\n",
    "        (j, s, minval, c1, c2) = self._divide(x, y, feature_count)\n",
    "        # 初始化树\n",
    "        tree = {\"feature\": j, \"value\": x[s, j], \"left\": None, \"right\": None}\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] <= x[s, j])]) <= 1:\n",
    "            tree[\"left\"] = c1\n",
    "        else:\n",
    "            tree[\"left\"] = self._fit(x[np.where(x[:, j] <= x[s, j])],\n",
    "                                     y[np.where(x[:, j] <= x[s, j])],\n",
    "                                     self.feature_count, self.epsilon)\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] > s)]) <= 1:\n",
    "            tree[\"right\"] = c2\n",
    "        else:\n",
    "            tree[\"right\"] = self._fit(x[np.where(x[:, j] > x[s, j])],\n",
    "                                      y[np.where(x[:, j] > x[s, j])],\n",
    "                                      self.feature_count, self.epsilon)\n",
    "        return tree\n",
    "\n",
    "    def fit(self):\n",
    "        self.tree = self._fit(self.x, self.y, self.feature_count, self.epsilon)\n",
    "\n",
    "    @staticmethod\n",
    "    def _divide(x, y, feature_count):\n",
    "        # 初始化损失误差\n",
    "        cost = np.zeros((feature_count, len(x)))\n",
    "        # 公式5.21\n",
    "        for i in range(feature_count):\n",
    "            for k in range(len(x)):\n",
    "                # k行i列的特征值\n",
    "                value = x[k, i]\n",
    "                y1 = y[np.where(x[:, i] <= value)]\n",
    "                c1 = np.mean(y1)\n",
    "                y2 = y[np.where(x[:, i] > value)]\n",
    "                c2 = np.mean(y2)\n",
    "                y1[:] = y1[:] - c1\n",
    "                y2[:] = y2[:] - c2\n",
    "                cost[i, k] = np.sum(y1 * y1) + np.sum(y2 * y2)\n",
    "        # 选取最优损失误差点\n",
    "        cost_index = np.where(cost == np.min(cost))\n",
    "        # 选取第几个特征值\n",
    "        j = cost_index[0][0]\n",
    "        # 选取特征值的切分点\n",
    "        s = cost_index[1][0]\n",
    "        # 求两个区域的均值c1,c2\n",
    "        c1 = np.mean(y[np.where(x[:, j] <= x[s, j])])\n",
    "        c2 = np.mean(y[np.where(x[:, j] > x[s, j])])\n",
    "        return j, s, cost[cost_index], c1, c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\ProgramData\\Anaconda3\\lib\\site-packages\\numpy\\core\\fromnumeric.py:3335: RuntimeWarning: Mean of empty slice.\n",
      "  out=out, **kwargs)\n",
      "C:\\ProgramData\\Anaconda3\\lib\\site-packages\\numpy\\core\\_methods.py:161: RuntimeWarning: invalid value encountered in double_scalars\n",
      "  ret = ret.dtype.type(ret / rcount)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'feature': 0,\n",
       " 'value': 5,\n",
       " 'left': {'feature': 0, 'value': 3, 'left': 4.72, 'right': 5.57},\n",
       " 'right': {'feature': 0,\n",
       "  'value': 7,\n",
       "  'left': {'feature': 0, 'value': 6, 'left': 7.05, 'right': 7.9},\n",
       "  'right': {'feature': 0, 'value': 8, 'left': 8.23, 'right': 8.85}}}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train_X = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]).T\n",
    "y = np.array([4.50, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00])\n",
    "\n",
    "model_tree = LeastSqRTree(train_X, y, .2)\n",
    "model_tree.fit()\n",
    "model_tree.tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上面程序的输出，可得到用平方误差损失准则生成一个二叉回归树：$$f(x)=\\begin{cases}\n",
    "4.72 & x \\le 3\\\\\n",
    "5.57 & 3 < x \\le 5\\\\\n",
    "7.05 & 5 < x \\le 6\\\\\n",
    "7.9 & 6 < x \\le 7 \\\\\n",
    "8.23 & 7 < x \\le 8\\\\\n",
    "8.85 & x > 8\\\\\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题5.3\n",
    "\n",
    "&emsp;&emsp;证明 CART 剪枝算法中，当$\\alpha$确定时，存在唯一的最小子树$T_{\\alpha}$使损失函数$C_{\\alpha}(T)$最小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "**第1步：**内部节点是否剪枝只与以该节点为根节点的子树有关。  \n",
    "剪枝过程：  \n",
    "计算子树的损失函数：$$C_{\\alpha}(T)=C(T)+\\alpha$$其中，$\\displaystyle C(T) = \\sum_{t=1}^{|T|}N_t (1 - \\sum_{k=1}^K (\\frac{N_{tk}}{N_t})^2)$，$|T|$是叶结点个数，$K$是类别个数。  \n",
    "有剪枝前子树$T_0$，剪枝后子树$T_1$，满足$C_{\\alpha}(T_1) \\leqslant C_{\\alpha}(T_0)$则进行剪枝。 \n",
    "\n",
    "----\n",
    "\n",
    "**第2步（反证法）：**假设当$\\alpha$确定时，存在两颗子树$T_1,T_2$都使得损失函数$C_{\\alpha}$最小。  \n",
    "第1种情况：假设被剪枝的子树在同一边，易知其中一个子树会由另一个子树剪枝而得到，故不可能存在两个最优子树，原结论得证。  \n",
    "第2种情况：假设被剪枝的子树不在同一边，易知被剪枝掉的子树都可以使损失函数$C_{\\alpha}$最小，故两颗子树都可以继续剪枝，故不可能存在两个最优子树，原结论得证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题5.4\n",
    "\n",
    "&emsp;&emsp;证明 CART 剪枝算法中求出的子树序列$\\{T_0,T_1,\\cdots,T_n\\}$分别是区间$\\alpha \\in [\\alpha_i,\\alpha_{i+1})$的最优子树$T_{\\alpha}$，这里$i=0,1,\\cdots,n,0=\\alpha_0 < \\alpha_1 < \\cdots, \\alpha_n < +\\infty$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "原结论可以表述为：将$\\alpha$从小增大，$0=\\alpha_0<\\alpha_1<\\cdots<\\alpha_n < +\\infty$，在每个区间$[\\alpha_i,\\alpha_{i+1})$中，子树$T_i$是这个区间里最优的。  \n",
    "**第1步：**易证，当$\\alpha=0$时，整棵树$T_0$是最优的，当$\\alpha \\rightarrow +\\infty$时，根结点组成的单结点树（即$T_n$）是最优的。\n",
    "\n",
    "----\n",
    "\n",
    "**第2步：**  \n",
    "&emsp;&emsp;由于每次剪枝剪的都是某个内部结点的子结点，也就是将某个内部结点的所有子结点回退到这个内部结点里，并将这个内部结点作为叶子结点。因此在计算整体的损失函数时，这个内部结点以外的值都没变，只有这个内部结点的局部损失函数改变了，因此本来需要计算全局的损失函数，但现在只需要计算内部结点剪枝前和剪枝后的损失函数。  \n",
    "从整体树$T_0$开始剪枝，对$T_0$的任意内部结点$t$    \n",
    "剪枝前的状态：有$|T_t|$个叶子结点，预测误差是$C(T_t)$  \n",
    "剪枝后的状态：只有本身一个叶子结点，预测误差是$C(t)$\n",
    "因此剪枝前的以$t$结点为根结点的子树的损失函数是$$C_{\\alpha}(T_t) = C(T_t) + \\alpha|T_t|$$剪枝后的损失函数是$$C_{\\alpha}(t) = C(t) + \\alpha$$易得，一定存在一个$\\alpha$使得$C_{\\alpha}(T_t) = C_{\\alpha}(t)$，这个值为$$\\alpha=\\frac{C(t)-C(T_t)}{|T_t|-1}$$可知，找到$\\alpha$即找到了子结点$t$，即完成了剪枝，得到最优子树$T_1$  \n",
    "根据书中第73页，采用以下公式计算剪枝后整体损失函数减少的程度：$$g(t)=\\frac{C(t)-C(T_t)}{|T_t|-1}$$在$T_0$中剪去$g(t)$最小的$T_t$，将得到的子树作为$T_1$，同时将最小的$g(t)$设为$\\alpha_1$，$T_1$为区间$[\\alpha_1,\\alpha_2)$的最优子树。  \n",
    "依次类推，子树$T_i$是区间$[\\alpha_i,\\alpha_{i+1})$里最优的，原结论得证。\n",
    "\n",
    "----\n",
    "\n",
    "**参考文献：**  \n",
    "1. MrTriste：https://blog.csdn.net/wjc1182511338/article/details/76793164\n",
    "2. http://www.pianshen.com/article/1752163397/\n",
    "\n",
    "----\n",
    "\n",
    "**讨论：**为什么$\\alpha$要取最小的$g(t)$呢？  \n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);width: 354px;\" src=\"../images/5-1-min-g(t).png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图5.1 最小的$g(t)$</div></center>  \n",
    "&emsp;&emsp;以图中两个点为例，结点1和结点2，$g(t)_2$大于$g(t)_1$，假设在所有结点中$g(t)_1$最小，$g(t)_2$最大，两种选择方法：当选择最大值$g(t)_2$，即结点2进行剪枝，但此时结点1的剪枝前的误差大于剪枝后的误差，即如果不剪枝，误差变大，依次类推，对其它所有的结点的$g(t)$都是如此，从而造成整体的累计误差更大。反之，如果选择最小值$g(t)_1$，即结点1进行剪枝，则其余结点不剪的误差要小于剪枝后的误差，不剪枝为好，且整体的误差最小。从而以最小$g(t)$剪枝获得的子树是该$\\alpha$值下的最优子树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "参考代码：https://github.com/wzyonggege/statistical-learning-method\n",
    "\n",
    "本文代码更新地址：https://github.com/fengdu78/lihang-code\n",
    "\n",
    "习题解答：https://github.com/datawhalechina/statistical-learning-method-solutions-manual\n",
    "\n",
    "中文注释制作：机器学习初学者公众号：ID:ai-start-com\n",
    "\n",
    "配置环境：python 3.5+\n",
    "\n",
    "代码全部测试通过。\n",
    "![gongzhong](../gongzhong.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
